package question1_5;

import java.util.Arrays;
import java.util.HashMap;

/**
 * @description: 找出数组中重复的数据
 *  在一个长度为n的数组里，所有的数字都在0~n-1范围内，数组中某些数字是重复的，
 *  但不知道有几个数字重复了，也不知道每个数字重复了几次。
 *  要求：找出数组中任意一个重复的数字
 * @author: jhy
 * @time: 2021/5/10 18:34
 */


public class Question3_1 {

    public static void main(String[] args) {

        int[] nums = {2,3,1,0,2,3,5};
        Question3_1 question3_1 = new Question3_1();
        //int dupNum = question3_1.solution1(nums, nums.length);
        //int dupNum = question3_1.solution2(nums, nums.length);
        int dupNum = question3_1.solution3(nums, nums.length);
        System.out.println(dupNum);

    }


    //方法1：先将数组排序然后遍历有序数组，即可很容易找到重复数字
    //时间复杂度:O(nlogn) 空间复杂度:O(1)
    //参数：nums-->要找重复数据的数组  n-->数组长度
    public int solution1(int[] nums,int n){

        Arrays.sort(nums);  //也可以自己写快排
        for(int i = 1;i < n;i++){
            if(nums[i] == nums[i-1]){
                return nums[i];
            }
        }
        return -1;
    }


    //2.方法2:只要看到要判断是否重复，就可以想到HashMap
    //hashmap中键存数组中的数据，值随便
    //遍历数组，每遍历一个数据，就判断该数据是否在HashMap中出现过，如果出现过，直接返回该数据，否则，将该数据加入HashMap
    //时间复杂度:O(n)  空间复杂度O(n)
    public int solution2(int[] nums,int n){
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        for(int i = 0;i < n;i++){
            if(hashMap.containsKey(nums[i])){
                return nums[i];
            }
            hashMap.put(nums[i],1);
        }
        return -1;
    }


    //方法3:本题的特殊之处：数组长度为n并且数组的值在0~n-1范围
    //如果数组中没有重复数字，那么当数组排好序之后，数字i将出现在数组下标为i的位置
    //思路：遍历数组，当扫描到下标为i的数字时，如果 i == nums[i] ,说明nums[i]在它应该在的位置，接着扫描下一个数字
    //     如果i != nums[i] ,那么我们将nums[i] 与nums[nums[i]]进行比较，
    //                  如果相同，则找到了一个重复数据，
    //                  如果不相同，就将这两个数据交换位置，将nums[i]放在它应该在的位置
    //     重复这个比较、交换的过程，直到找到重复数据或者数组遍历完毕
    //代码中尽管有两个循环，但每个数字最多交换两次就能找到属于它的位置，所以总的时间复杂度为O(n)
    public int solution3(int[] nums,int n){

        //从头到尾遍历数组
        for(int i = 0;i < n;i++){
            while (i != nums[i]){
                if(nums[i] == nums[nums[i]]){
                    return nums[i];
                }else {
                    int temp = nums[i];
                    nums[i] = nums[temp];
                    nums[temp] = temp;
                }
            }
        }
        return -1;
    }

}
